#include <stdio.h>
#include <malloc.h>
struct node
{
	int num;
	struct node *next;
};

typedef struct
{
	struct node *start;
	int noe;
}list;

void list_append(list *a, int num)
{
	if(a->start==NULL)
	{
		a->start = (struct node *)malloc(sizeof(struct node));
		a->start->num = num;
		a->start->next = NULL;
		a->noe = 1;
	}	
	else
	{
		struct node* ptr = a->start;
		while(ptr->next!=NULL)
			{
				ptr = ptr->next;
			}
		ptr->next = (struct node *)malloc(sizeof(struct node));
		ptr->next->num = num;
		ptr->next->next = NULL;
		a->noe++;
	}	
}

int list_pop(list *a, int index)
{
	if(index >= a->noe || index < 0)
	{
		printf("\nERROR: Invalid Index!");
		return;
	}
	struct node* ptr = a->start;
	if(ptr==NULL)
	{
		return;
	}
	if(index==0)
	{
		int temp = ptr->num;
		struct node* t = ptr;
		a->start = ptr->next; 
		free(t);
		printf("\nThe Number popped is: %d\n", temp);
		return temp;
	}
	else
	{	
		int c = 0;
		while(c!=index - 1)
		{
			ptr = ptr->next;
			c++;
		}
		int temp = ptr->next->num;
		struct node *t = ptr->next;
		ptr->next = ptr->next->next;
		free (t);
		printf("\nThe Number popped is: %d\n", temp);
		return temp;
	}
}

//The insert function. The value of the position is the value of the index AT which you want the new element. 
void list_insert(list *a, int x, int pos)
{	
	if(pos > a->noe)
	{
		printf("\nERROR: Invalid Index!");
		return;
	}
	else if(pos==0)
	{
	struct node *t = (struct node *)malloc(sizeof(struct node));
	t->next = a->start;
	a->start = t;
	t->num = x;
	a->noe++;	
	}
	else
	{
	struct node *ptr = a->start;
		int i=0;
		for(i=0; i < pos - 1 ; i++)
		{
			ptr = ptr->next;
		}
	struct node *t = (struct node *)malloc(sizeof(struct node));
	t->next = ptr->next;
	t->num = x;
	ptr->next = t;
	a->noe++;
	}
}

void list_extend(list *a, list *b)
{
	struct node *ptr = a->start;
	while(ptr->next!=NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = b->start;
	a->noe += b->noe;
	
}

void list_remove(list *a)
{
	int temp;
	printf("\nPlease enter the element to be removed: ");
	scanf("%d", &temp);
	
	int flag=0;
	
	struct node *ptr = a->start;

	if(ptr->num==temp)
	{
		a->start = a->start->next;
		free(ptr);
	}
	else
	{
		while(ptr->next!=NULL)
		{
			if(ptr->next->num == temp)
			{
				flag = 1;
				break;
			}
			ptr=ptr->next;
		}		
		if(flag==1)
		{
			struct node *t = ptr->next;
			ptr->next = ptr->next->next;
			free(t);
		}
		else
		{
			printf("\nERROR: Element not found!");
		}
	}
}

int list_index(list* a, int ele)
{
	int index = -1;
	int c=0;	
	struct node *ptr = a->start;
	while(ptr!=NULL)
	{
		if(ptr->num == ele)
		{
			index = c;
			break;
		}
		c++;
		ptr=ptr->next;
	}
	return index;
}

int list_count(list *a, int ele)
{
	struct node *ptr = a->start;
	int c = 0;
	while(ptr!=NULL)
	{
		if(ptr->num==ele)
		{ c++; }
		ptr = ptr->next;
	}
	return c;
}

void insert_sorted(list *b, int ele)
{
	struct node* start = b->start;
	
	if(start==NULL)
		{
			b->start = (struct node*)malloc(sizeof(struct node));
			b->start->num = ele;
			b->start->next = NULL;
			b->noe++;
		}
	else
		{
		
			struct node *t;
			struct node *cur = start;
			if(start->num >= ele)
			{
				t = start;
				start = (struct node*)malloc(sizeof(struct node));
				start->num = ele;
				start->next = t;
			}				
			else 
			{while(cur->next!=NULL && cur->next->num <= ele)
			{
				cur = cur->next;
			}
			t = (struct node*)malloc(sizeof(struct node));
			t->next = cur->next;
			t->num = ele;
			cur->next = t;
			}	
			b->noe++;
		}
}

list list_sort(list *a)
{

	list *b = (list *)malloc(sizeof(list)); b->start = NULL; b->noe = 0;
	struct node* ptr = a->start;

	while(ptr!=NULL)
	{
		insert_sorted(b, ptr->num);
		ptr = ptr->next;
	}
	return *b;
}

void list_reverse(list *a)
{
	struct node * *or = (struct node **)malloc(a->noe * sizeof(list *));
	int c = 0;
	struct node* ptr;	
	ptr = a->start;
	while(ptr!=NULL)
	{	
		or[c] = ptr;
		ptr = ptr->next;
		c++;
	}
	c--;	
	a->start = or[c];
	ptr = a->start;
	while(c!=0)
	{
		ptr->next = or[c];
		ptr = ptr->next;
		c--;
	}
	ptr->next = or[0];
	ptr->next->next = NULL;
	
	
	

}

void generate_list(list *a)
{
	printf("\nPlease enter the number of items you want to enter: ");
	int c, i, temp;
	int j;
	scanf("%d", &c);
	i = 1;	
	while(i<=c)
	{
		printf("\nElement %d: ", i);
		scanf("%d", &temp);
		list_append(a, temp);
		i++;
	}	
}

void display_list(list a)
{
	printf("[ ");
	if(a.noe !=0)
	{
	struct node *ptr = a.start;
	while(ptr->next!=NULL)	
	{
		printf("%d, ", ptr->num);
		ptr = ptr->next;
	}
	printf("%d ]\n", ptr->num);
	}
	else
	{ printf(" ]\n"); }
}

void main()
{
	list a; a.start = NULL; a.noe = 0;

	generate_list(&a);
	int ch=1;

	printf("\n\n\t\t\tWelcome to the List Program!\n\t This program implements the list data structure using Linked Lists!\n\n");

	while(ch!=0)
	{
	printf("\n\nPlease choose an option\n\t\t1. Append an Element\n\t\t2. Pop an Element\n\t\t3. Extend The List\n\t\t4. Remove an Element\n\t\t5. Find Index of an element\n\t\t6. Count the instances of an element\n\t\t7. Sort the list\n\t\t8. Reverse the List\n\t\t9. Insert an Element\n\t\t0. Exit");
	printf("\n\nCurrent state of list is: ");	
	display_list(a);
	printf("\nYour choice: ");
	scanf("%d", &ch);

	switch(ch){
	case 0:{ break; }
	case 1:{ printf("\nPlease enter the element you want to append: "); int temp; scanf("%d", &temp); list_append(&a, temp); break;}
	case 2:{ printf("\nPlease enter the index you want to pop: "); int temp; scanf("%d", &temp); list_pop(&a, temp); break;}
	case 3:{ list b; b.start = NULL; b.noe = 0; generate_list(&b); printf("\nThe Intermediate list is: "); display_list(b); printf("\nThe Original list will now be extended by concatenating with this list!"); list_extend(&a, &b); break; }
	case 4:{ list_remove(&a); break; }
	case 5:{ int t; printf("Please enter the element who's index you want to find: "); scanf("%d", &t); int temp = list_index(&a, t); if(temp==-1) printf("\n\nThe Element doesn't exist!"); else {printf("\n\nThe index of the element is: %d", temp);} break;}
	case 6:{ int t; printf("Please enter the element who's count you want to find: "); scanf("%d", &t); int temp = list_count(&a, t); if(temp==0) printf("\n\nThe Element doesn't exist!"); else {printf("\n\nThe count of the element is: %d", temp);}  break;}
	case 7:{ a = list_sort(&a); break;}
	case 8:{ list_reverse(&a); break;}
	case 9:{ int i, x; printf("\nPlease enter the index at which you want to insert: "); scanf("%d", &i); printf("Please enter the element to insert: "); scanf("%d", &x); list_insert(&a, x, i); break;}
	default: { printf("\nInvalid choice!"); break; } }
	}

}
